UVa/10067 - Playing with wheels/10067.cpp

   1 #include <iostream>
   2 #include <queue>
   3 #include <vector>
   4 #include <sstream>
   5
   6
   7 using namespace std;
   8
   9 inline string intToStr(const int &n){stringstream ss; ss<<n; string s; ss>>s; return s; }
  10 inline int strToInt(const string &n){stringstream ss; ss<<n; int s; ss>>s; return s; }
  11
  12 int main(){
  13   int cases;
  14   cin >> cases;
  15   while (cases--){
  16     vector<bool> forbidden(10000, false);
  17     vector<bool> visited(10000, false);
  18
  19
  20     int start = 0;
  21     for (int i=0; i<4; ++i){
  22       int x; scanf("%d", &x);
  23       start = (start * 10) + x;
  24     }
  25
  26     int end = 0;
  27     for (int i=0; i<4; ++i){
  28       int x; scanf("%d", &x);
  29       end = (end * 10) + x;
  30     }
  31
  32     int n;
  33     cin >> n;
  34     while (n--){
  35       int f=0;
  36       for (int i=0; i<4; ++i){
  37         int x; scanf("%d", &x);
  38         f = (f * 10) + x;
  39       }
  40       forbidden[f] = true;
  41     }
  42
  43     queue<pair<int, int> > q;
  44     int answer = -1;
  45     q.push(make_pair(start, 0));
  46     while (!q.empty()){
  47       int node = q.front().first;
  48       int dist = q.front().second;
  49       q.pop();
  50       if (node == end){
  51         answer = dist;
  52         break;
  53       }
  54       if (visited[node]){
  55         continue;
  56       }
  57       visited[node] = true;
  58       for (int i=0; i<4; ++i){
  59         stringstream ss;
  60         ss << node;
  61         string s;
  62         ss >> s;
  63         string t;
  64         char digit;
  65         int neighbour;
  66
  67         t = s;
  68         digit = s[i];
  69         digit = '0' + ((digit - '0' + 1) % 10);
  70         t[i] = digit;
  71         //cout << "t es: " << t << endl;
  72         //cout << "neighbour es: " << strToInt(t) << endl;
  73         neighbour = strToInt(t);
  74         if (!forbidden[neighbour]){
  75           q.push(make_pair(neighbour, dist + 1));
  76           //cout << "Empuje " << q.front().first << endl;
  77         }
  78
  79         t = s;
  80         digit = s[i];
  81         digit = '0' + ((digit - '0' + 9) % 10);
  82         t[i] = digit;
  83         neighbour = strToInt(t);
  84         //cout << "neighbour es: " << strToInt(t) << endl;
  85         if (!forbidden[neighbour]){
  86           q.push(make_pair(neighbour, dist + 1));
  87           //cout << "Empuje " << q.front().first << endl;
  88         }
  89       }
  90     }
  91     cout << answer << endl;
  92
  93   }
  94   return 0;
  95 }